In computer science, a tree is a hierarchical data structure of linked nodes. A tree is an acyclic connected graph in which each node in the tree has zero or more child nodes and at most one parent node. A node may contain a value, a condition, or may represent a separate data structure (such as another tree). By convention a child node is “below” its parent in the tree, which is to say, computer science trees, unlike trees in nature, grow down instead of up. A node that has a child is called the child's parent node, its ancestor or its superior node.
A tree is represented in a computer by nodes in memory and references that represent the edges in the tree. Each parent node has a reference to its child node(s), but not every child node has a reference to it parent node. A node that has no children is called a leaf node or a terminal node. The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). The topmost node in a tree is called the root node. The root node does not have a parent. Operations on a tree commonly begin at the root node. Any node in the tree can be reached from the root node by following pointers or links between nodes. An operation is frequently performed when a particular node in the tree is reached. An internal node is any node of a tree that has child nodes. Thus a leaf node is not an internal node because a leaf node has no child nodes.
Each node in a tree can be seen as the root node of the subtree that descends from that node. The term “subtree” refers to a tree consisting of a node in the tree and all the descendants of that node in the tree. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree. Trees can be represented in many different ways. Some common representations represent a node as a record allocated on the heap (not to be confused with the heap data structure) with pointer(s) to its child node(s), its parent, or to both child node(s) and parent node, or as an item in an array, with relationships between nodes determined by the position of the nodes in the array (e.g., a binary heap).
A tree can be traversed by following connections or pointers between a series of parent nodes and the parents' child node(s). A pre-order traversal arrives at a parent node before it reaches the parent node's child node(s). A post-order traversal is one in which the child nodes of a parent node are traversed before the parent node is traversed.
A parse tree or syntax tree is typically an ordered, rooted tree that represents the syntactic structure of a string according to some formal grammar. In a parse tree, the interior nodes are labeled by non-terminals of the grammar, while the leaf nodes are labeled by terminals of the grammar. One type of program that produces such trees is called a parser. Parse trees or syntax trees are frequently generated during processing of computer programming languages.